package datastructure.bstnew;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二分搜索树
 *
 * @param <E> 泛型
 */
public class BST<E extends Comparable<E>> {
    private int size;
    private Node root;

    public BST() {
        size = 0;
        root = null;
    }

    /**
     * 添加元素
     *
     * @param e 元素
     */
    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }
        return node;
    }

    /**
     * 是否包含元素e
     *
     * @param e 元素e
     * @return 是否有
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(Node root, E e) {
        if (root == null) {
            return false;
        }
        if (e.compareTo(root.e) < 0) {
            return contains(root.left, e);
        } else if (e.equals(root.e)) {
            return true;
        } else {
            return contains(root.left, e);
        }
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.println(root.e);
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.e);
    }
//    private void add(Node root, E e) {
//        if (e.equals(root.e)){
//            return;
//        }else if (e.compareTo(root.e) < 0 && root.left == null){
//            root.left = new Node(e);
//        } else if (e.compareTo(root.e) > 0 && root.right == null){
//            root.right = new Node(e);
//        }
//        if (e.compareTo(root.e) < 0){
//            add(root.left, e);
//        } else {
//            add(root.right, e);
//        }
//    }

    /**
     * 二分搜索树的前序遍历，非递归实现
     */
    public void preOrderNR() {
        Stack<Node> stack = new Stack<>();
        if (root != null) {
            stack.push(root);
        }
        preOrderNR(stack);
    }

    private void preOrderNR(Stack<Node> stack) {
        // 栈为空时作为终止条件
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            // 每次出栈，先压入非空的右左孩子（注意顺序）
            System.out.println(node.e);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    /**
     * 二叉树的层序遍历
     */
    public void orderInLine() {
        // 先定义个队列
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node cur = queue.remove();
            // 移除队首元素后，把改结点的左右孩子入队尾，注意顺序啊，先左后右
            System.out.println(cur.e);
            if (cur.left != null)
                queue.add(cur.left);
            if (cur.right != null)
                queue.add(cur.right);
        }
    }

    /**
     * 寻找最小元素
     *
     * @return 最小元素
     */
    public E minElement() {
        if (root == null) {
            throw new IllegalArgumentException("二分搜索树为空");
        }
        Node min = minElement(root);
        return min.e;
    }

    private Node minElement(Node root) {
        if (root.left == null) {
            return root;
        }
        return minElement(root.left);
    }

    /**
     * 寻找最大元素
     *
     * @return 最大元素
     */
    public E maxElement() {
        if (root == null) {
            throw new IllegalArgumentException("二分搜索树为空");
        }
        Node max = maxElement(root);
        return max.e;
    }

    private Node maxElement(Node root) {
        if (root.right == null) {
            return root;
        }
        return minElement(root.right);
    }

    public E removeMin() {
        E e = minElement();
        root = removeMin(root);
        return e;
    }

    private Node removeMin(Node node) {
        if (node.left == null) {
            E e = node.e;
            Node right = node.right;
            node.right = null;
            size--;
            return right;
        }
        E e = node.e;
        node.left = removeMin(node.left);
        return node;
    }

    public E removeMax() {
        E e = maxElement();
        root = removeMax(root);
        return e;
    }

    private Node removeMax(Node node) {
        if (node.right == null) {
            Node left = node.left;
            node.left = null;
            size--;
            return left;
        }
        node.right = removeMax(node.right);
        return node;
    }

    public void removeElem(E e) {
        if (!contains(e)) {
            return;
        }
        removeElem(root, e);
    }

    private Node removeElem(Node node, E e) {
        if (node == null) {
            return null;
        }
        if (e.compareTo(node.e) < 0) {
            node.left = removeElem(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = removeElem(node.right, e);
            return node;
        } else {
            if (node.left == null) {
                Node right = node.right;
                node.right = null;
                size--;
                return right;
            }
            if (node.right == null) {
                Node left = node.left;
                node.left = null;
                size--;
                return left;
            }
            // 左右都不为空
            Node successor = minElement(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;
            return successor;
        }
    }

    /**
     * 是否为空
     *
     * @return 是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获取元素个数
     *
     * @return 元素个数
     */
    public int getSize() {
        return size;
    }

    private class Node {
        E e;
        Node left;
        Node right;

        public Node(E e) {
            this.e = e;
        }
    }

}
